#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int countPrimes(int n) {
        vector<bool>str(n);
        vector<int>prime;
        int cnt=0;
        for(int i=2;i<n;i++)
        {
            if(!str[i])prime.push_back(i);
            for(int j=0;j<prime.size()&&prime[j]<n/i;j++)
            {
                str[i*prime[j]]=true;
                if(i%prime[j]==0)break;
            }
        }
        return prime.size();
    }
};
int main()
{
    Solution s1;
    s1.countPrimes(10);
}